package leetcode;

import java.util.HashSet;
import java.util.Set;

//滑动窗口
public class LeetCode3 {

    //滑动窗口
    //重点理解 hashset就是滑动窗口 每次重复后移动起始位置，直到hashset不重复再移动j
    public int myLengthOfLongestSubstring(String s) {
        int result = 0, i = 0, j = 0;
        Set<Character> dict = new HashSet<>();
        while (i < s.length() && j < s.length()) {
            char c = s.charAt(j);
            if (!dict.contains(c)) {
                dict.add(c);
                j++;
                //每次更新 防止跳出循环
                result = Math.max(result, j - i);
            } else {
                dict.remove(s.charAt(i));
                i++;
            }
        }
        return result;
    }

    //优化版的滑动窗口
    //bug 没有删除i+1前的记录
    public int myLengthOfLongestSubstring1(String s) {
        int[] dict = new int[128];
        int result = 0, i = 0, j = 0;
        while (i < s.length() && j < s.length()) {
            if (dict[s.charAt(j)] == 0) {
                dict[s.charAt(j)] = j;
                j++;
                result = Math.max(result, j - i);
            } else {
                //i之前的数据都要清除
                i = dict[s.charAt(j)] + 1;
                dict[s.charAt(j)] = j;
                j++;
            }
        }
        return result;
    }

    public int lengthOfLongestSubstring1(String s) {
        int n = s.length();
        Set<Character> set = new HashSet<>();
        int ans = 0, i = 0, j = 0;
        while (i < n && j < n) {
            // try to extend the range [i, j]
            if (!set.contains(s.charAt(j))){
                set.add(s.charAt(j++));
                ans = Math.max(ans, j - i);
            }
            else {
                set.remove(s.charAt(i++));
            }
        }
        return ans;
    }

    //思路3没有看明白
    public int lengthOfLongestSubstring2(String s) {
        int n = s.length(), ans = 0;
        int[] index = new int[128]; // current index of character
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; j++) {
            i = Math.max(index[s.charAt(j)], i);
            ans = Math.max(ans, j - i + 1);
            index[s.charAt(j)] = j + 1;
        }
        return ans;
    }
}
